1. Field of the Invention
The invention relates generally to data communications, and more particularly to data switching arrangements.
2. Description of Related Art
Recent developmental efforts have focused upon feedback-based flow control in the operational environment of high-speed, wide-area ATM networking. In particular, an explicit rate-based approach has been studied extensively and adopted by the ATM Forum as a standard for the flow control of Available Bit Rate (ABR) service. An illustrative rate-based flow control problem may be stated as follows, with reference to FIG. 1. Consider a network 100 that includes a plurality of nodes 102, 104, 106, 108. (These nodes 102, 104, 106, 108 could also be conceptualized as representing switches.). A first source 110 at a first geographic location transmits data into node 102, and a second source 112 at a second geographic location transmits data into node 104.
The first source 110 transmits data into node 102 at a data transfer rate allocated by node 102, and the second source transmits data into node 104 at a data transfer rate allocated by node 104. Node 102 allocates a data transfer rate to first source 110 based upon a virtual circuit path 115 over which data from node 102 is to travel, and node 104 allocates a data transfer rate to second source 112 based upon a virtual circuit path 117 over which data from node 104 is to travel. In allocating data transfer rates among sources 110, 112, each node 102, 104, 106, 108 computes the rate that will be allocated to each of the active sources whose virtual circuit path is routed through that node 102, 104, 106, 108. These computed rates are conveyed from a given node 102, 104, 106, 108 to the sources connected to that node via a data structure termed a resource management (RM) cell.
An RM cell is generated by, and transmitted on, a given virtual circuit path 115 by a source 110. The RM cell includes a data field that contains the minimum circuit path 115 to the source 102 during a round trip of data from the source 102 to a destination source, and back to source 102 along the virtual circuit path 115. For a wide-area network in which the end-to-end round-trip propagation delay is relatively large, the rate allocation carried by an RM cell may no longer be valid in view of the current status of the network, and so immediate, real-time flow control cannot be performed. In this scenario, there is an increasing likelihood of cell loss and link under-utilization. Particularly as link speed increases (i.e., the speed of the communications links connecting a pair of nodes 102, 104), this problem becomes more serious, due to the large bandwidth-delay product involved in the closed loop.
Methods by which a node processor allocates data transfer rates are classified are into one of two types: queue-length-based rate control, and explicit rate allocation. In queue-length-based rate control, the rate to a source is calculated as a function of the difference between the queue length and the queue threshold, based on the measurement of the queue length. In this type of approach, a desired fairness in rate allocation (e.g., MAX-MIN fairness) among sources is accomplished as a consequence of the queue-length control. Examples of this type of algorithm are found in F. Bonomi, D. Mitra and J. B. Seery, "Adaptive Algorithms for Feedback-Based Flow Control in High-Speed, Wide-Area Networks", IEEE J. Select. Areas on Communications, Vol. 13, No. 7, Sep. 1995, pp. 1267-1283, and S. Mascolo, D. Cavendish and M. Gerla, "ATM Rate Based Congestion Control Using a Smith Predictor: an EPRCA Implementation", Proc. of IEEE INFOCOM '96, March 1996, pp. 569-576. In an explicit rate allocation approach, instead of controlling the queue-length explicitly, the switch computes the rate to a source based on an asynchronous distributed algorithm that is designed to accomplish a desired fairness in rate allocation. Examples of this type of algorithm are found in L. Kalampoukas, A. Varma and K. K. Ramakrishnan, "An Efficient Rate Allocation Algorithm for ATM Networks Providing Max-Min Fairness," Technical Report UCSC-CRL-95-29, Computer Engineering Dept., University of California, Santa Cruz, June 1995, and D. Bertsekas and R. Gallager, Data Networks, Prentice Hall, 1992.